package list

import (
	"errors"
	"fanshuai-go/common"
	"strconv"
)

type SingleList struct {
	head *Node
	tail *Node
	size int
}

func NewSingleList() *SingleList {
	list := SingleList{size: 0}
	node := Node{data: nil}
	list.head = &node
	list.tail = &node

	return &list
}

func (s *SingleList) Size() int {
	return s.size
}

func (s *SingleList) IsEmpty() bool {
	return s.size == 0
}

func (s *SingleList) Capacity() int {
	return 1<<31 - 1
}

func (s *SingleList) Add(i interface{}) {
	node := &Node{data: i}

	s.tail.next = node
	s.tail = node
	s.size++
}

func (s *SingleList) AddIndex(index int, data interface{}) {
	if index < 0 || index > s.size {
		panic(errors.New("index out of bounds, index=" + strconv.Itoa(index)))
	}

	node := &Node{data: data}

	t := s.head
	for j := 0; j < index; j++ {
		t = t.next
	}

	node.next = t.next
	t.next = node
	s.size++

	if index == s.size {
		s.tail = node
	}
}

func (s *SingleList) Remove(data interface{}) {
	if s.size == 0 {
		return
	}
	p := s.head
	cur := s.head.next

	for cur.next != nil {
		if cur.data == data {
			break
		}
		p = cur
		cur = cur.next
	}

	if cur != nil {
		if cur == s.tail {
			s.tail = p
		}
		p.next = cur.next
		cur.next = nil
		s.size--
	}
}

func (s *SingleList) RemoveIndex(index int) {
	if index < 0 || index > s.size-1 {
		panic(errors.New("index out of bounds, index=" + strconv.Itoa(index)))
	}

	p := s.head
	cur := s.head.next

	for i := 0; i < index; i++ {
		p = cur
		cur = cur.next
	}

	if cur == s.tail {
		s.tail = p
	}
	p.next = cur.next
	cur.next = nil
	s.size--
}

func (s *SingleList) Get(index int) interface{} {
	if index < 0 || index > s.size-1 {
		panic(errors.New("index out of bounds, index=" + strconv.Itoa(index)))
	}

	if s.size == 0 {
		panic(errors.New("list empty"))
	}

	cur := s.head.next
	for i := 0; i < index; i++ {
		cur = cur.next
	}

	return cur.data
}

func (s *SingleList) IndexOf(i interface{}) int {
	index := -1

	if s.size == 0 {
		return -1
	}

	node := s.head.next
	for node != nil {
		index++
		if i == node.data {
			return index
		}

		node = node.next
	}

	return -1
}

func (s *SingleList) AddAll(list List) {
	ite := s.Iterator()
	for ite.HasNext() {
		data := ite.Next()
		s.Add(data)
	}
}

func (s *SingleList) Clear() {
	s.size = 0
	node := &Node{data: nil}

	s.head = node
	s.tail = node
}

func (s *SingleList) Iterator() common.Iterator {
	return NewSingleListIterator(s)
}

type SingleListIterator struct {
	list *SingleList
	node *Node
}

func NewSingleListIterator(list *SingleList) *SingleListIterator {
	iterator := SingleListIterator{}
	iterator.list = list
	iterator.node = list.head.next

	return &iterator
}
func (a *SingleListIterator) HasNext() bool {
	return a.node != nil
}

func (a *SingleListIterator) Next() interface{} {
	data := a.node.data
	a.node = a.node.next
	return data
}

type LinkedList struct {
	head *DoubleNode
	tail *DoubleNode
	size int
}

func NewLinkedList() *LinkedList {
	node := &DoubleNode{data: nil}

	list := &LinkedList{size: 0}
	list.head = node
	list.tail = node
	return list
}

func (l *LinkedList) Size() int {
	return l.size
}

func (l *LinkedList) IsEmpty() bool {
	return l.size == 0
}

func (l *LinkedList) Capacity() int {
	return 1<<31 - 1
}

func (l *LinkedList) Add(i interface{}) {
	node := &DoubleNode{data: i}

	l.tail.next = node
	node.pre = l.tail
	l.tail = node

	l.size++
}

func (l *LinkedList) AddIndex(index int, data interface{}) {
	if index < 0 || index > l.size {
		panic(errors.New("index out of bounds, index=" + strconv.Itoa(index)))
	}

	node := &DoubleNode{data: data}

	cur := l.head
	for i := 0; i < index; i++ {
		cur = cur.next
	}

	next := cur.next

	node.next = next
	if next != nil {
		next.pre = node
	}

	cur.next = node
	node.pre = cur
	l.size++

	if index == l.size {
		l.tail = node
	}
}

func (l *LinkedList) Remove(data interface{}) {
	if l.size == 0 {
		return
	}

	cur := l.head.next
	for cur != nil {
		if cur.data == data {
			break
		}

		cur = cur.next
	}

	if cur != nil {
		pre := cur.pre
		if cur == l.tail {
			l.tail = pre
		}

		pre.next = cur.next
		if cur.next != nil {
			cur.next.pre = pre
		}

		cur.next = nil
		cur.pre = nil
		l.size--
	}
}

func (l *LinkedList) RemoveIndex(index int) {
	if index < 0 || index > l.size-1 {
		panic(errors.New("index out of bounds, index=" + strconv.Itoa(index)))
	}
	if l.size == 0 {
		panic(errors.New("list empty"))
	}

	cur := l.head.next
	for i := 0; i < index; i++ {
		cur = cur.next
	}

	pre := cur.pre
	if cur == l.tail {
		l.tail = pre
	}

	pre.next = cur.next
	if cur.next != nil {
		cur.next.pre = pre
	}

	cur.pre = nil
	cur.next = nil
	l.size--
}

func (l *LinkedList) Get(index int) interface{} {
	if index < 0 || index > l.size-1 {
		panic(errors.New("index out of bounds, index=" + strconv.Itoa(index)))
	}
	if l.size == 0 {
		panic(errors.New("list empty"))
	}

	cur := l.head.next
	for i := 0; i < index; i++ {
		cur = cur.next
	}

	return cur.data
}

func (l *LinkedList) IndexOf(data interface{}) int {
	if l.size == 0 {
		return -1
	}

	cur := l.head.next

	i := 0
	for cur != nil {
		if cur.data == data {
			return i
		}
		cur = cur.next
		i++
	}

	return -1
}

func (l *LinkedList) AddAll(list List) {
	ite := l.Iterator()

	for ite.HasNext() {
		data := ite.Next()
		l.Add(data)
	}
}

func (l *LinkedList) Clear() {
	node := &DoubleNode{data: nil}

	l.head = node
	l.tail = node
	l.size = 0
}

func (l *LinkedList) Iterator() common.Iterator {
	return NewLinkedListIterator(l)
}

type LinkedListIterator struct {
	list *LinkedList
	node *DoubleNode
}

func (ite *LinkedListIterator) HasNext() bool {
	return ite.node != nil
}

func (ite *LinkedListIterator) Next() interface{} {
	data := ite.node.data
	ite.node = ite.node.next
	return data
}

func NewLinkedListIterator(l *LinkedList) *LinkedListIterator {
	ite := LinkedListIterator{}
	ite.list = l
	ite.node = l.head.next

	return &ite
}
